//除自身以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n+1,1);
        auto g = f;
        for(int i = 1 ; i <= n ; ++i)
        {
            f[i] = f[i-1]*nums[i-1];
        }
        for(int i = n-1 ; i > 0 ; --i)
        {
            g[i] = g[i+1]*nums[i];
        }
        vector<int> ret(n);
        for(size_t i = 0 ; i < n ; ++i)
        {
            ret[i] = g[i+1]*f[i];
        }
        return ret;
    }
};

//和为k的子数组
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
       int n = nums.size();
       unordered_map<int,int> hash;
       hash[0] = 1;
       int sum = 0 , ret = 0;
       for(size_t i = 0 ; i < n ; ++i)
       {
           sum += nums[i];
           if(hash.count(sum-k))
           {
               ret+=hash[sum-k];
           }
           hash[sum]++;
       }
       return ret;
    }
};

